package leetcode.递归回溯BFSDFS;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 组合总和 II
 * candidates 中的每个数字在每个组合中只能使用一次。
 * 给出的数组里面的元素可以重复存在
 * <p>
 * 再试一次
 * 注意：i++ 与 i+1不一样
 * <p>
 * i++ 和 i += 1 是等价的，支持自动类型转换
 * 但是他们和 i = i + 1 不等价，这种方式不支持自动类型转换，+ 运算符会将 short 提升为 int，再把 int 赋值给 short 会编译报错的
 */
public class Test40组合总和II {

    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        if (candidates.length == 0) {
            return res;
        }
        List<Integer> list = new ArrayList<>();
        backTrace(res, list, candidates, target, 0);
//        backTrace2(res, list, candidates, target, new boolean[candidates.length], 0);
        return res;
    }

    public static void backTrace(List<List<Integer>> res, List<Integer> list
            , int[] nums, int remain, int start) {
        if (remain < 0)
            return;
        if (remain == 0) {
            res.add(new ArrayList<>(list));
        } else {
            for (int i = start; i < nums.length; i++) {
                // 排序之后可以很方便的去重，防止产生相同的 list
                // 其原理是：回溯之后 i 一定增加了，但是 start 维持不变（但是 start != i - 1）
                // 若此时的 i 和上一次的 i 相同的话可以直接跳过不需要再计算了
                if (i > start && nums[i] == nums[i - 1]) {
                    // i > start 的意思是回溯之后，
                    // 发现这次处理的 i 和上次的一样，则不处理
                    continue;
                }
                list.add(nums[i]);
                // 避免同一元素重复使用，i要从下一个开始
                backTrace(res, list, nums, remain - nums[i], i + 1);
                list.remove(list.size() - 1);
            }
        }
    }

    // 错误的例子，不能像全排列一样搞
    public static void backTrace2(List<List<Integer>> res, List<Integer> tmp
            , int[] nums, int target, boolean[] visited, int start) {
        if (target < 0)
            return;
        if (target == 0) {
            if (!res.contains(new ArrayList<>(tmp)))
                res.add(new ArrayList<>(tmp));
            return;
        }
        // 这种从 0 开始的遍历方式会导致同一个数字被重复使用很多次
        // 所以不能从 0 开始
        for (int i = start; i < nums.length; i++) {
            if (!visited[i]) {
                tmp.add(nums[i]);
                visited[i] = true;
                backTrace2(res, tmp, nums, target - nums[i], visited, 1);
                tmp.remove(tmp.size() - 1);
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args) {
//        int[] nums = {2, 5, 2, 1, 2};
//        int target = 5;
//        int[] nums = {10, 1, 2, 7, 6, 1, 5};
        int[] nums = {1, 1, 1, 3, 3, 5};
        int target = 8;
        System.out.println(combinationSum2(nums, target));

    }
}
